//TODO -> LeetCode215.数组中的第K个最大元素
//TODO -> https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

// 方法一：暴力排序
// 时间复杂度：O(NlogN) 空间复杂度：O(1)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //这里的第三个参数是一个lambda表达式，用于自定义排序规则
        sort(nums.begin(), nums.end(), [](int x, int y) {return x > y;});

        return nums[k - 1];
    }
};

// 方法二：堆的topK问题
// 时间复杂度：O(NlogK) 空间复杂度：O(K)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
        vector<int>::iterator it = nums.begin() + k;
        while(it != nums.end())
        {
            if(pq.top() < *it)
            {
                pq.pop();
                pq.push(*it);
            }
            ++it;
        }

        return pq.top();
    }
};

// 方法三：直接使用堆的特性
// 时间复杂度：O(NlogN) 空间复杂度：O(N)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(auto& x : nums)
        {
            pq.push(x);
        }

        while(--k)
        {
            pq.pop();
        }

        return pq.top();
    }
}